#include <bits/stdc++.h>
    using namespace std;

class Text
{
public:
    // 方法1：排序法（降序找第k-1位）
    int findKthLargest_sort(vector<int> &vtr, int k)
    {
        sort(vtr.rbegin(), vtr.rend()); 
        return vtr[k - 1];
    }

    // 方法2：快速选择
    int findKthLargest_kms(vector<int> &vtr, int k)
    {
        int idx = k - 1;                             
        pair<int, int> x = {0, (int)vtr.size() - 1}; 

        while (x.first < x.second)
        {
            int l = x.first - 1;      
            int r = x.second + 1;     
            int m = vtr[(l + r) >> 1];

            while (l < r)
            {
                do
                    l++;
                while (vtr[l] > m);
                do
                    r--;
                while (vtr[r] < m);

                if (l < r)
                    swap(vtr[l], vtr[r]);
            }

            if (idx <= r)
                x = {x.first, r};
            else
                x = {r + 1, x.second}; 
        }

        return vtr[x.first];
    }
};

// 生成n个随机整数（1~1e9）
vector<int> generate_random_data(int n)
{
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<int> dis(1, 1e9);
    vector<int> data(n);
    generate(data.begin(), data.end(), [&]()
             { return dis(gen); });
    return data;
}

// 性能测试：多规模多轮测试，输出到文件
void test_performance(Text &t, ofstream &fout)
{
    vector<int> sizes = {10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000, 500000, 1000000, 5000000, 10000000}; // 测试规模
    int num_tests = 20;                                   // 每组测试次数

    // 输出表头（格式化）
    fout << string(80, '=') << endl;
    fout << left << setw(10) << "规模"
         << setw(10) << "测试次"
         << setw(20) << "排序法耗时(ms)"
         << setw(20) << "快速选择耗时(ms)"
         << endl;
    fout << string(80, '-') << endl;

    for (int n : sizes)
    {
        vector<long long> sort_durations, kms_durations;

        for (int i = 0; i < num_tests; ++i)
        {
            // 生成数据并复制两份（避免方法干扰）
            vector<int> original = generate_random_data(n);
            vector<int> data_sort = original;
            vector<int> data_kms = original;

            // 随机选k（1~n）
            int k = rand() % n + 1;

            // 测试排序法
            auto start_sort = chrono::steady_clock::now();
            t.findKthLargest_sort(data_sort, k);
            auto end_sort = chrono::steady_clock::now();
            long long dur_sort = chrono::duration_cast<chrono::microseconds>(end_sort - start_sort).count();
            sort_durations.push_back(dur_sort);

            // 测试快速选择
            auto start_kms = chrono::steady_clock::now();
            t.findKthLargest_kms(data_kms, k);
            auto end_kms = chrono::steady_clock::now();
            long long dur_kms = chrono::duration_cast<chrono::microseconds>(end_kms - start_kms).count();
            kms_durations.push_back(dur_kms);

            // 输出单次结果（毫秒，保留3位小数）
            fout << left << setw(10) << n
                 << setw(10) << (i + 1)
                 << setw(20) << fixed << setprecision(3) << (dur_sort / 1000.0)
                 << setw(20) << (dur_kms / 1000.0)
                 << endl;
        }

        // 计算平均耗时
        double avg_sort = accumulate(sort_durations.begin(), sort_durations.end(), 0.0) / num_tests / 1000.0;
        double avg_kms = accumulate(kms_durations.begin(), kms_durations.end(), 0.0) / num_tests / 1000.0;

        // 输出平均结果
        fout << string(80, '-') << endl;
        fout << left << setw(10) << "平均"
             << setw(10) << ""
             << setw(20) << fixed << setprecision(3) << avg_sort
             << setw(20) << avg_kms
             << endl;
        fout << string(80, '=') << endl
             << endl;
    }
}

// 正确性验证
void correctness_check(Text &t)
{
    cout << "===== 正确性测试 =====" << endl;

    // 测试用例1：LeetCode 215样例
    vector<int> v1 = {3, 2, 1, 5, 6, 4};
    int k1 = 2;
    int res1_sort = t.findKthLargest_sort(v1, k1);
    int res1_kms = t.findKthLargest_kms(v1, k1);
    cout << "规模6，k=2：排序法=" << res1_sort << "，快速选择=" << res1_kms << "（预期：5）" << endl;

    // 测试用例2：重复元素
    vector<int>
        v2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};
    int k2 = 4;
    int res2_sort = t.findKthLargest_sort(v2, k2);
    int res2_kms = t.findKthLargest_kms(v2, k2);
    cout << "规模9，k=4：排序法=" << res2_sort << "，快速选择=" << res2_kms << "（预期：4）" << 
    endl;

    cout
        << "===== 正确性测试通过 =====" << endl
        << endl;
}

void score()
{
    Text t;
    srand(time(0));
    ofstream fout("time_results.txt");

    if (!fout)
        return;

    correctness_check(t);

    // 2. 性能测试
    cout << "===== 开始性能测试（结果将写入time_results.txt） =====" << endl;
    test_performance(t, fout);
    cout << "===== 性能测试完成 =====" << endl;

    fout.close();
}

int main(int argc, const char *argv[])
{
    int t = 1;
    // cin >> t;
    while (t--)
        score();
    return 0;
}